class Solution {
public:
    char nextGreatestLetter(vector<char>& letters, char target) {
        /*
        if(target>=letters[letters.size()-1]||target<letters[0]){
            return letters[0];
        }
        
        int left=0;
        int right=letters.size()-1;
        int mid=0;
        while(true){
            mid=(right-left)%2==0?left+(right-left)/2:left+(right-left)/2+1;
            if(letters[mid]>target&&letters[mid-1]<=target){
                break;
            } else if(target>=letters[mid]){
                left=mid;
            } else{
                right=mid;
            }
            //cout<<"left"<<left<<",mid:"<<mid<<",right"<<right<<endl;
        }
        return letters[mid];
        */
        int len=letters.size();
        int left=0;
        int right=len-1;
        int mid=0;
        while(left<=right){
            mid=(left+right)/2;
            if(target<letters[mid]){
                right=mid-1;
            } else{
                left=mid+1;
            }
            //cout<<"left:"<<left<<",mid:"<<mid<<",right:"<<right<<endl;
        }
        return letters[left%len];
    }